/*
 * com.future CO.,ltd.
 */

package com.future;

/**
 * Description: 517. ����ϴ�»�
 * ������ n?̨����ϴ�»�����ͬһ���ϡ���ʼ��ʱ��ÿ̨ϴ�»��ڿ�����һ�������·���Ҳ�����ǿյġ�
 * ��ÿһ�������У������ѡ������ m (1 <= m <= n) ̨ϴ�»������ͬʱ��ÿ̨ϴ�»���һ���·��͵����ڵ�һ̨ϴ�»���
 * ����һ����������?machines �����������ÿ̨ϴ�»��е������������������������ϴ�»���ʣ�µ������������ȵ� ���ٵĲ������� ��
 * �������ʹÿ̨ϴ�»��������������ȣ��򷵻� -1 ��
 * <p>
 * ʾ�� 1��
 * <p>
 * ���룺machines = [1,0,5]
 * �����3
 * ���ͣ�
 * ��һ��:    1     0 <-- 5    =>    1     1     4
 * �ڶ���:    1 <-- 1 <-- 4    =>    2     1     3
 * ������:    2     1 <-- 3    =>    2     2     2
 * <p>
 * ��Դ�����ۣ�LeetCode��
 * ���ӣ�https://leetcode-cn.com/problems/super-washing-machines
 * ����Ȩ������������С���ҵת������ϵ�ٷ���Ȩ������ҵת����ע��������
 *
 * @Author: future
 * @Date:2022/4/16:11:22
 */
public class Solution_517 {

    public static void main(String[] args) {
        int[] machine = {10, 2, 3, 1, 4};
        machine = new int[]{0, 3, 0};
        machine = new int[]{9, 1, 8, 8, 9};
        System.out.println(findMinMoves(machine));
    }

    /**
     * =======���1��
     * 0,..,i-1,ȱa��(��-a��ʾ)
     * i+1,..,��b��(��+b��ʾ)
     * ��ôi������Math.max(a,b)��
     * =======���2��
     * 0,..,i-1, +a
     * i+1,.., -b
     * ��ôi������Math.max(a,b)��
     * =======���3��
     * 0,..,i-1, +a
     * i+1,.., +b
     * ��ôi������(a+b)��
     * =======���4��
     * 0,..,i-1, -a
     * i+1,.., -b
     * ��ôi������(a+b)��
     * <p>
     * ****���ۣ�i=0,1,..,
     * ****��һ����Ҫ�Ĳ����������ô�;��Ǵ�
     * @param machines
     * @return
     */
    public static int findMinMoves(int[] machines) {
        if (machines == null || machines.length == 0) {
            return -1;
        }
        int N = machines.length;
        int[] sumArr = new int[N];
        sumArr[0] = machines[0];
        for (int i = 1; i < N; i++) {
            sumArr[i] += sumArr[i - 1] + machines[i];
        }
        if (sumArr[N - 1] % N != 0) {
            return -1;
        }
        int ans = 0;
        int avg = sumArr[N - 1] / N;
        for (int i = 0; i < N; i++) {
            /**
             * leftRest��i����߻���Ҫ����/�Ƴ����ټ���>0��ʾ��Ҫ�Ƴ����٣�<0��ʾ��Ҫ���䣩
             * sumArr[i-1]��0,...,i-1ǰһ���ۼӺ�
             * i * avg��0,...,i-1,�ܹ�i������ƽ������ܸ���
             */
            int leftRest = i > 0 ? (sumArr[i - 1] - i * avg) : 0;
            /**
             * i���ұ߻���Ҫ����/�Ƴ����ټ���>0��ʾ��Ҫ�Ƴ����ټ���<0��ʾ��Ҫ���䣩
             */
            int rightRest = (sumArr[N - 1] - sumArr[i]) - avg * (N - i - 1);
            if (leftRest < 0 && rightRest < 0) {
                /**
                 * ��ʾiλ����Ҫ�Ƴ���������һ��������ͬʱ���������ƶ��·����������
                 */
                ans = Math.max(ans, Math.abs(leftRest + rightRest));
            } else {
                leftRest = Math.abs(leftRest);
                rightRest = Math.abs(rightRest);
                ans = Math.max(ans, Math.max(leftRest, rightRest));
            }
        }
        return ans;
    }
}
